SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Datafly algorithm</title>

</head>

Datafly algorithm

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">Datafly algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> for providing anonymity in medical data. The algorithm was developed by <a href="Latanya_Arvette_Sweeney" class="mw-redirect" title="Latanya Arvette Sweeney">Latanya Arvette Sweeney</a> in 1997−98.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> Anonymization is achieved by automatically generalizing, substituting, inserting, and removing information as appropriate without losing many of the details found within the data. The method can be used on-the-fly in <a href="Role-based_access_control" title="Role-based access control">role-based</a> security within an institution, and in <a href="Batch_processing" title="Batch processing">batch</a> mode for <a href="Import_and_export_of_data" title="Import and export of data">exporting data</a> from an institution.

Organizations release and receive medical data with all explicit <a href="Identifier" title="Identifier">identifiers</a>—such as name—removed, in the erroneous belief that <a href="Physician%E2%80%93patient_privilege" title="Physician–patient privilege">patient confidentiality</a> is maintained because the resulting data look anonymous. However the remaining data can be used to re-identify individuals by linking or matching the data to other databases or by looking at unique characteristics found in the <a href="Field_(computer_science)" title="Field (computer science)">fields</a> and <a href="Row_(database)" title="Row (database)">records</a> of the <a href="Database" title="Database">database</a> itself.

The Datafly algorithm has been criticized for trying to achieve anonymization by overgeneralization. The algorithm selects the <a href="Attribute_(computing)" title="Attribute (computing)">attribute</a> with the greatest number of distinct <a href="Value_(computer_science)" title="Value (computer science)">values</a> as the one to generalize first.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Core_algorithm">Core algorithm</h2></div>

An outline of the Datafly algorithm is presented below.<a href="#cite_note-4">[4]</a>

<a href="Input_(computer_science)" title="Input (computer science)">Input</a>:

Private <a href="Table_(database)" title="Table (database)">Table</a> PT; <a href="Quasi-identifier" title="Quasi-identifier">quasi-identifier</a> QI = ( A1, ..., An ), k-anonymity constraint k; domain generalization hierarchies DGHAi, where i = 1,...,n with accompanying <a href="Function_(mathematics)" title="Function (mathematics)">functions</a> fAi, and loss, which is a limit on the percentage of <a href="Tuple" title="Tuple">tuples</a> that can be suppressed. PT[id] is the set

of unique identifiers or keys for each tuple.

<a href="Output_(computing)" class="mw-redirect" title="Output (computing)">Output</a>:

MGT a generalization of PT[QI] that enforces k-anonymity

Assumes: | PT | ≤ k, and loss * | PT | = k

algorithm Datafly:

// Construct a frequency <a href="List_(abstract_data_type)" title="List (abstract data type)">list</a> containing unique <a href="Sequence" title="Sequence">sequences</a> of values across the quasi-identifier in PT,

// along with the number of occurrences of each sequence.

<dl><dd>1. let freq be an expandable and collapsible <a href="Vector_(mathematics_and_physics)" title="Vector (mathematics and physics)">vector</a> with no elements initially. Each element is of the form ( QI, frequency, SID ), where SID = { idi : ∃ t[id] ∈ [id] ⇒ t[id] = idi }; and, frequency = |SID|. Therefore, freq is also accessible as a table over (QI, frequency, SID).</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> 0, total <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gets }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> 0</dd></dl>

<dl><dd>3. while total ≠ |PT| do</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> ( t[QI], occurs, SID ) where t[QI] ∈ [QI], ( t[ QI ],__, ___ ) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \not \in }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \not \in }</annotation>

</semantics>

</math><img src="./c681ffd934198bd2f57aa31518fd119ceeb0e6d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.55ex; height:2.676ex;" alt="{\displaystyle \not \in }" loading="lazy"> freq; occurs = |PT| - |PT[QI] – {t[QI]}|; and, SID = { idi : ∃ t[id] <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gets }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> PT[id] ⇒ t[id] = idi }</dd></dl></dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> pos + 1, total <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gets }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> total + occurs</dd></dl></dd></dl>

<dl><dd>// Make a solution by generalizing the attribute with the most number of distinct values</dd></dl>

<dl><dd>// and suppressing no more than the allowed number of tuples.</dd></dl>

<dl><dd>4. let belowk <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gets }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> 0</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> 1 to |freq| do</dd></dl>

<dl><dd><dl><dd>5.1 ( __, count ) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gets }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> freq[pos]</dd></dl></dd></dl>

<dl><dd><dl><dd>5.2 if count < k then do</dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd>5.2.1 belowk <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gets }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> belowk + count</dd></dl></dd></dl></dd></dl>

<dl><dd>6. if belowk > k then do: // Note. loss * |PT| = k.</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> generalize(freq)</dd></dl></dd></dl>

<dl><dd>// assert: the number of tuples to suppress in freq is ≤ loss * |PT|</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> suppress(freq, belowk )</dd></dl></dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gets }</annotation>

</semantics>

</math><img src="./1c2dd7a1d3a3f2df940296f2485c2e10355b16f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \gets }" loading="lazy"> reconstruct(freq)</dd></dl></dd></dl>

<dl><dd>8. return MGT.</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLatanya_Sweeney" class="citation web cs1">Latanya Sweeney. <a rel="nofollow" class="external text" href="http://dataprivacylab.org/datafly/">"Datafly: a system for providing anonymity in medical data"</a>. Retrieved 19 January 2014.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> L. Sweeney, Datafly: a system for providing anonymity in medical data. Database Security, XI: Status and Prospects, T. Lin and S. Qian (eds), Elsevier Science, Amsterdam, 1998.<a rel="nofollow" class="external autonumber" href="http://dataprivacylab.org/datafly/paper2.pdf">[1]</a>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFXiong" class="citation web cs1"><a href="Li_Xiong_(computer_scientist)" title="Li Xiong (computer scientist)">Xiong, Li</a>. <a rel="nofollow" class="external text" href="http://www.mathcs.emory.edu/~lxiong/cs573_s12/share/slides/0131_generalization_slawek.pdf">"Data Anonymization - Generalization Algorithms"</a> (PDF). Retrieved 19 January 2014.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFLatanya_Sweeney2001" class="citation thesis cs1">Latanya Sweeney (2001). Computational Disclosure Control A Primer on Data Privacy Protection (Thesis). MIT. p. 113. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F8589">1721.1/8589</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://cs.utdallas.edu/dspl/cgi-bin/toolbox/javadoc/datafly/Datafly.html">Details of the Datafly algorithm</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-12-09" href="https://en.wikipedia.org/wiki/?title=Datafly_algorithm&oldid=1189130380">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>